1. Field of the Invention
This invention relates to methods for automated design of electronic devices, and more particularly, to methods for maintaining regularity in electronic circuit designs while increasing synthesis speed and quality.
2. Background of Related Art
The increasing complexity of microelectronic designs and the continuous development of fabrication processes, yielding smaller layouts, presents new challenges to existing design automation tools. It is widely acknowledged that future electronic design automation methodologies must be able to handle the challenges and opportunities inherent in very large designs. This particularly applies to the field of logic synthesis, as existing design sizes already present a considerable challenge to current synthesis tools.
Future synthesis tools are expected to handle millions of gates in a reasonable amount of time. However, traditional logic synthesis is not able to satisfy these increasing demands. Due to the amount of available topological and functional transformations and their non-incremental nature, it is generally difficult and computationally expensive to select an optimal subset of transformations and their respective sequence. Therefore, current synthesis methodologies rely mainly on the concept of trial and error, applying sequences of transformations until a satisfactory arrangement is found. This process, however, produces a tradeoff between efficiency and quality and generally, does not yield optimal results. In addition, results vary depending on the actual designs, hence the overall optimization is left to the experienced designer.
In logic synthesis of large designs, efficiency in determining places to apply transformations to the design is a desired goal. When a transform succeeds at a certain place, it would be desirable to apply it quickly at other places in the design with the same characteristics.
Another important challenge of logic synthesis is the preservation of regular design structures during the optimization process. Maintaining regularity has significant advantages to the physical design stages. In particular, placing regular structures in rows and columns, yields a much denser layout, decreasing wire length and delay, and simplifying the overall placement task. In addition, the layout of a regular design is more predictable at an early design stage. The extraction of regularity and its usage has been exploited and used extensively to obtain high-density layouts in placement. Special placement techniques, such as datapath placement, have been developed to take advantage of regular structures.
While it is widely acknowledged that generic logic synthesis destroys a substantial amount of structural regularity, particularly during logic minimization and technology mapping, previously published approaches focus on the extraction of regularity. The problem of maintaining regularity throughout the design flow has rarely been addressed, and to date, no known solutions have been presented. A commonly used concept to avoid destruction of regularity is to skip logic minimization and map the technology by manual assignment of library cells. This process not only demands a substantial amount of manual work, it is also unable to benefit from potential improvements in logic minimization algorithms and is therefore generally undesirable.
In conclusion, a need exists for methods to efficiently synthesize logic netlists while maintaining regularity and achieving high quality designs.
A method for maintaining regularity in a netlist according to the present invention determines a structural regularity. The method determines a group of structures having similar regularity signatures. In one embodiment of the present invention, a method for maintaining regularity in a netlist is described. The method determines structural regularity. In one step, the method applies transformations to all elements of a stage within a regular group. In another step, the method determines regularity signatures for all elements of that stage. The method also compares the regularity signatures of all elements of the stage to determine whether the regularity signatures are identical. Further, the method, upon determining that the regularity signatures are different, removes any changes applied by the transformation to the netlist.
In another embodiment of the invention, a method to speed up the logic synthesis of a netlist is described. The method determines regularity signatures for elements of a netlist. Furthermore, the method identifies a beneficial transformation to a place in the network. In another step, the method re-applies the same transformation to all others places which have an equivalent regularity signature.
According to yet another embodiment of the present invention, a method for maintaining regularity in a netlist during logic synthesis is disclosed. The method determines a global regularity for the netlist, determines a group of elements in the netlist having similar regularity signatures, and applies a transform to the group of elements.
The method further, determines a regularity signature for each element within the group, and determines whether the regularity signatures for each element are identical, if the signatures are different the method removes the changes to the netlist made by the transform.
The method is performed for each stage in the order of dataflow through the netlist.
The global regularity is determined by the method in accordance with the following relationship:       RI    p    =                    1                  Aavg          ·                      (                                          n                grp                            +                              n                nr                                      )                              ·              (                                            ∑                              i                =                1                                            n                nr                                      ⁢                          xe2x80x83                        ⁢                          A                              nr                i                                              +                                    ∑                              i                =                1                                            n                grp                                      ⁢                          xe2x80x83                        ⁢                          (                                                A                                      grp                    j                                                  ·                                                      2                    ·                                                                  A                                                  grp                          j                                                                                                                                                h                      i                                        +                                          w                      i                                                                                  )                                      )              -    1  
where: RIp is the physical regularity index measuring the amount of global regularity that effectively improves area and delay cost functions in the final physical layout; ngrp is the number of regular groups; nnr is the number of gates which are not assigned to a regular group; h is the group height; w is the group width; Aavg is the average physical area of a gate in the design; Anri is the area of gate i not assigned to a regular group; and Agrpj is the area of the regular group, j.
The method classifies each element into a signature class according to regularity signatures. The method also identifies a place in the netlist to improve, identifies a class method when an improvement can be made, applies the class method to each class member, determines whether the class method is successful, and upon determining that the class method is unsuccessful, removes the changes made by the class method. The method also updates regularity signatures and classes.
According to the current embodiment, the method identifies the class method by applying a plurality of transforms to the place. The method determines which transform achieves a defined solution, and defines the successful transform as the class method.
The method determines success according to whether the regularity signatures for each class member are identical after the application of the class method.
An element, according to the method, includes a net, a gate, or both a net and a gate. The regularity signature includes a logic signature, a time signature, an area signature or a power signature. The regularity signature includes an adaptive signature for controlling changes in the netlist made by the transform. According to the method, the transform applies an action.
In yet another embodiment of the present invention, a method for maintaining regularity in a netlist during logic synthesis determines a global regularity for the netlist based on regularity, symmetry or dataflow. The method determines a group of elements having similar local regularity signatures within the netlist, applies a transform to the group of elements, and determines whether the local regularity signatures for each element are identical, removing changes to the netlist made by the transform if the signatures are different.
An element can include a net, a gate, or both a net and a gate. A local regularity signature includes a logic signature, a time signature, an area signature or a power signature, according to the method. The local regularity signature includes an adaptive signature for controlling changes in the netlist made by the transform. According to the method, a transform applies an action.
In yet another embodiment of the present invention, a method for maintaining regularity in a netlist during logic synthesis, includes calculating a regularity signature for each of a plurality of elements in the netlist. The method classifies elements into signature classes based on the regularity signatures. The method identifies a place in the netlist for applying a class method. The method also identifies the class method for the place in the netlist. Further, the method applies the class method to a class member. The method determines the success of the class method based on whether the method achieved a desired regularity signature for the class member. The method also updates the regularity signatures and signature classes after all class members have been visited. The method continues to identify places in the netlist.
According to the method, the class method is a transform which is applied to each class member thereby preserving regularity in the netlist and providing an improved final netlist.
The regularity signature can be a logic signature, a time signature, an area signature or a power signature. According to the method, the local regularity signature includes an adaptive signature for controlling changes in the netlist made by the transform.
The method identifies the class method by determining a method which achieves a favorable result in the netlist based on a delay signature, an area signature, a timing signature, a power signature or logic signatures.
The method determines the success of the class method based on whether the method achieved the favorable result by applying the class method to each class member if successful. The method undoes the class method if unsuccessful.